Computer hardware is becoming increasingly distributed and remote, resulting in networks of computers for solving problems in concert rather than as stand-alone systems. Although such distributed "services" networks generally facilitate problem-solving, they also increase the need for flexibility and functionality in software programs operating on the computers.
An example of a distributed services computer network is a "client-server" system which comprises a collection of client nodes, e.g., workstations or personal computers, that communicate over a network with various server nodes. Each node is connected to the transmission medium at an address which uniquely identifies the node and which is used to route data from one node to another. The server nodes are typically computers having hardware and software elements that provide a sophisticated set of services, or operations, for use by the client nodes to increase the efficiency of their own operations. Several types of networks may be employed in the client-server system which are connected by one or more communication links that may be interconnected to other communication links and nodes within the network through bridges or routers.
Nodes coupled to the network typically communicate by exchanging messages which comprise discrete "packets" of data. These packets can be transported over the network with one of a variety of transport techniques. Asynchronous transfer mode (ATM) is a relatively new data transport technique in which the network transports and switches short, fixed-length units of information, called "cells". In applications utilizing ATM, data packets to be transported are first broken up into ATM cells, transmitted, and then reassembled at a destination. In accordance with current protocol, ATM cells are 53 bytes long. Each cell consists of a 5-byte header and a 48-byte information field. The header of an ATM cell contains the information used to transport the cell from one node to the next over a route which has been previously established by means of a separate signaling channel. User data is contained in the remaining 48 bytes.
The preestablished route over which the cells pass exists only as sets of routing tables held in each network node or switch, which tables determine the physical connection of the communication links. These routing tables are based on a virtual circuit identifier (VCI) code and a virtual path identifier (VPI) code contained in header of each ATM cell. When a virtual path is established, each node (or switch) is provided with a set of lookup tables that identify an incoming cell by the VCI and VPI codes in the header and then route it through the node to one of a plurality of output lines, so that the cell is sent to the proper connection and, ultimately, the proper destination.
In this manner, a cell is passed through each ATM switch and over each communication link via the pre-established route, but the route is considered "virtual" since the route carrying the cell is dedicated to it only while the cell traverses it. The physical facilities are shared among various routes. For example, two cells that are ultimately headed for different destinations may be sequentially carried for part of their journey over the same physical wire.
An important design objective in data packet or switch networks is controlling the flow of cells so that they do not arrive at communication links or switches at a faster rate than they can be processed and forwarded to the next destination. For example, a typical ATM switch acts as a cell relay. The input side of the switch contains a first in-first out buffer (FIFO) queue connected to the media input port. Cells arrive from the incoming communication link at an input data rate and are entered into one end of the buffer. The switching process involves examining each cell in turn at the other end of the buffer and determining from the VCI/VPI codes in the cell header which output line should be used. The cell is then added to a FIFO buffer queue for that output line which holds cells waiting to be transmitted on the associated outgoing communication link.
Switch congestion occurs when either the input or output FIFO buffers fill to a predetermined level. If the congestion becomes severe enough, the buffers may become completely full, in which case there is no space for incoming packets or cells to be stored and the packets or cells are lost. The cell loss problem is exacerbated because the flow of cells on the network is generally "bursty" in nature rather than steady. Most network applications operate independently of each other and generate a "burst" of data in response to some event such as a certain time of day or a user action. An example of a user action which generates network traffic is the generation of a "copy command" which starts a process that results in a data file being transported across the network. Such a copy command might generate one or many packets on a LAN which are eventually switched onto a backbone which connects to another LAN. For example, a typical Ethernet LAN packet of 1000 bytes would appear on the ATM backbone as a 60 microsecond burst of roughly 21 ATM cells.
Often, such bursts are widely separated from the previous and next burst of cells because the bursts are caused by independent events. Consequently, the average data rate, which is often calculated over the period of many milliseconds, can include much idle time and be much less that the peak data rate during a burst. However, in order to minimize cell loss, network devices are designed to accommodate the peak data rate of common traffic patterns. A common prior art technique is to design network equipment to be able to handle the expected peak data rate for unlimited time periods. This technique is effective but results in equipment which has expensive capacity that is not needed most of the time.
A typical switch design, for example an ATM network, uses a shared memory switch. In this type of switch, received cells at each of the input ports are demultiplexed (if necessary) and put onto queues located in a common cell memory. These queues take the form of linked lists in the common memory. Buffer memory is effectively allocated from the common memory pool as it is needed so that the output buffers which are represented by the queues can be of different lengths. Thus, the switch receives cells from a media input port and stores them in memory. Concurrently, the switch reads cells from the memory and forwards them to an output port for transmission on a medium. The memory is sized to buffer a sufficient number of cells in order to handle the bursty nature of the cell flow in the network. Such a memory typically has an input bandwidth which indicates the rate at which cells are stored and an output bandwidth which indicates the rate at which cells are forwarded. The overall memory throughput is generally the average of the input and output bandwidths.
Dual ported memories are commonly used for the common memory pool so that one memory port is used to store cells in the memory while the other memory port is used to forward cells out of the memory. However, a dual-port memory design requires arbitration between the input and output ports because the physical memory element cannot be simultaneously written and read. The cells are transferred much more quickly inside the switch than their arrival rate at the switch. Since each cell that arrives must also be forwarded, the shared memory element typically uses a round robin arbitration scheme between the input and output ports. In a traditional shared memory switch, round robin arbitration among the input and output ports results in a sequence of operations alternating between memory-write (cell store) and memory-read (cell forward). In addition, a round robin arbitration scheme is also used between the various input or output ports since only one input port can store at once and only one output port can read at once.
Since cells may arrive simultaneously at all input ports and there is a small process delay prior to storing the cell in the shared memory, a small first in-first out (FIFO) buffer is provided at each input port to the switch. The size of each input FIFO is normally very small, since the cost/bit of the FIFO buffer memories is high when compared to the cost/bit of the main shared memory. Cells that arrive from one input port are entered into one end of the FIFO input buffer connected to that port. The switching process involves examining each cell, in turn, at the other end of the FIFO input buffer and determining from the routing codes in the cell header which output port should be used. The cell is then added to a buffer queue in the main shared memory for that output port.
Such shared memory switches make efficient use of memory capacity. However, in a transient cell burst situation, it is possible for the input FIFO's to overload, resulting in input congestion and cell loss. Consequently, such a switch was conventionally designed to prevent the input FIFO's from overloading. This was accomplished by designing the shared memory so that its bandwidth exceeded the sum of the data rate input and output cell rates at all times, including peak loads.